{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 双链表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 双链表节点类，定义值和前后指向\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, prev=None, next=None):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.size = 0\n",
    "        \n",
    "    def addAtHead(self, val):                            # 添加头部节点\n",
    "        new_node = ListNode(val, None, self.head)        \n",
    "        if self.head:                                    ## 判断链表是否有节点\n",
    "            self.head.prev = new_node                    ## 有节点，则在当前头部前创建链接\n",
    "        else:\n",
    "            self.tail = new_node                         ## 无节点，则当前链表尾为创建节点\n",
    "        self.head = new_node                             ## 有节点，需设置链表头节点为新建节点\n",
    "        self.size +=1\n",
    "        \n",
    "    def addAtTail(self, val):                            # 添加尾部节点\n",
    "        new_node = ListNode(val, self.tail, None)        \n",
    "        if self.tail:                                    ## 判断链表是否有节点\n",
    "            self.tail.next = new_node                    ## 有节点，则在当前尾部后创建链接\n",
    "        else:\n",
    "            self.head = new_node                         ## 无节点，则当前链表头为创建节点\n",
    "        self.tail = new_node                             ## 有节点，需设置链表尾节点为新建节点\n",
    "        self.size +=1\n",
    "    \n",
    "    def get_val(self, index):                            # 值搜索——根据索引访问值\n",
    "        if index < 0 or index >= self.size:\n",
    "            return -1                                    ## 不合规索引输入\n",
    "        \n",
    "        if index < self.size//2:                         ## 向前向后探索选择：当索引在前半部分，从头部开始向后省时\n",
    "            cur = self.head\n",
    "            for i in range(index):\n",
    "                cur = cur.next\n",
    "        else:                                            ## 当索引在后半部分，从尾部开始向前省时\n",
    "            cur = self.tail\n",
    "            for i in range(self.size - index - 1):       ## 三个节点取最后，size=3,index=2,此时不应循环向前，因此还要-1\n",
    "                cur = cur.prev\n",
    "        return cur.val\n",
    "            \n",
    "    def addAtIndex(self, index, val):                    # 索引添加节点:索引插入位置对应链表箭头处\n",
    "        if index < 0 or index > self.size:               ## 添加节点可以在最后箭头处，所以可等于链表长度（搜索和删除则不行）\n",
    "            return                                       ## 不合规索引\n",
    "        \n",
    "        if index ==0:                                    ## 插入位置判断：头插入，尾插入，中间插入\n",
    "            self.addAtHead(val)                          ## 头插入\n",
    "        elif index == self.size:\n",
    "            self.addAtTail(val)                          ## 尾插入\n",
    "        else:                                            ## 中间插入\n",
    "            if index < self.size//2:                     ## 向前向后选择\n",
    "                cur = self.head\n",
    "                for i in range(index-1):                 ## 向后中间插入：指针需在插入位置前一个节点（index-1）,为使新节点向前链接\n",
    "                    cur = cur.next\n",
    "            else:\n",
    "                cur = self.tail\n",
    "                for i in range(self.size-index):         ## 向后中间插入：三个节点，插入index=2(最后节点前插入)，size=3,则需获倒数二的节点\n",
    "                    cur = cur.prev\n",
    "            new_node = ListNode(val, cur, cur.next)      ## 创建新节点\n",
    "            cur.next.prev = new_node                     ## 新节点向后链接\n",
    "            cur.next = new_node                          ## 新节点向前链接\n",
    "            self.size +=1\n",
    "            \n",
    "    def deleteAtIndex(self, index):                      # 索引删除节点\n",
    "        if index < 0 or index >= self.size:\n",
    "            return                                       ## 不合规索引\n",
    "        \n",
    "        if index==0:                                     ## 删除位置判断：头删除，尾删除，中间删除\n",
    "            self.head = self.head.next                   ## 头节点换为下一节点\n",
    "            if self.head:\n",
    "                self.head.prev = None                    ## 删除头后链表还有节点，将当前头的前链接断开\n",
    "            else:\n",
    "                self.tail = None                         ## 删除头后无节点，设为空链表\n",
    "        elif index == self.size-1:\n",
    "            self.tail = self.tail.prev                   ## 尾节点换为上一节点\n",
    "            if self.tail:\n",
    "                self.tail.next = None\n",
    "            else:\n",
    "                self.head = None\n",
    "        else:\n",
    "            if index < self.size // 2:                  ## 向前向后方向判断\n",
    "                current = self.head\n",
    "                for i in range(index):                  ## 指针指向删除索引位置\n",
    "                    current = current.next\n",
    "            else:\n",
    "                current = self.tail\n",
    "                for i in range(self.size - index - 1):  ## 指针指向删除索引位置：三个节点取最后，size=3,index=2,此时不应循环向前，因此还要-1\n",
    "                    current = current.prev\n",
    "            current.prev.next = current.next            ## 断开删除节点前链接\n",
    "            current.next.prev = current.prev            ## 断开删除节点后链接\n",
    "        self.size -= 1\n",
    "        \n",
    "    def print_list(self):\n",
    "        cur_node = self.head\n",
    "        print(\"None\", end=\" <-> \")\n",
    "        while cur_node:\n",
    "            print(cur_node.val, end=\" <-> \")\n",
    "            cur_node = cur_node.next\n",
    "        print(\"None\")                                   ## 遍历链表打印\n",
    "        print(self.size)                                ## 打印当前链表长度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 1 <-> None\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "LinkedList = MyLinkedList()\n",
    "\n",
    "#创建头节点\n",
    "LinkedList.addAtHead(1)\n",
    "LinkedList.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 1 <-> 2 <-> 3 <-> None\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "#尾添加节点\n",
    "LinkedList.addAtTail(2)\n",
    "LinkedList.addAtTail(3)\n",
    "LinkedList.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, -1)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LinkedList.get_val(1),LinkedList.get_val(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 1 <-> 2 <-> 3 <-> 5 <-> None\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "LinkedList.addAtIndex(3,5)\n",
    "LinkedList.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> None\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "LinkedList.addAtIndex(3,4)\n",
    "LinkedList.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 2 <-> 3 <-> 4 <-> 5 <-> None\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "LinkedList.deleteAtIndex(0)\n",
    "LinkedList.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 2 <-> 3 <-> 4 <-> None\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "LinkedList.deleteAtIndex(3)\n",
    "LinkedList.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None <-> 2 <-> 4 <-> None\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "LinkedList.deleteAtIndex(1)\n",
    "LinkedList.print_list()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
